package medium

import (
	. "GoLeetcode/common"
	"container/heap"
	"sort"
)

/*
时间复杂度:O(NlogN)
空间复杂度:O(logN)

单调队列(小根堆/大根堆)

问题:如何贪心选择使得可以参加的会议最多??
解决:1.将所有会议按开始时间从小到大排序,这样可以优先参加更早开始的会议
	2.通过curDate记录当前参加的会议是第几天,然后将所有开始时间为curDate的会议的结束时间放入小根堆中,这样堆顶就是结束时间最早的会议
	3.如果有多个会议开始时间相同,则我们贪心的选择结束时间最早的,因为结束时间更晚的可选择的机会更多
*/

func maxEvents(events [][]int) int {
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})
	n := len(events)
	idx := 0
	curDate := 1
	result := 0
	h := new(Heap)
	heap.Init(h)
	for idx < n || h.Len() > 0 {
		// 将开始时间为curDate的所有会议的结束时间压入heap中
		for idx < n && events[idx][0] == curDate {
			heap.Push(h, events[idx][1])
			idx++
		}
		// 如果heap中存在结束时间小于curDate的数据,表示该会议已经过期了,需要弹出
		for h.Len() > 0 && h.Arr[0] < curDate {
			heap.Pop(h)
		}

		// 上一步已经将结束时候<curDate的会议弹出了
		// 如果堆中还有元素,则堆顶元素肯定>=curDate,表示存在未结束的会议
		if h.Len() > 0 {
			result++
			heap.Pop(h)
		}
		curDate++
	}
	return result
}